package com.zrf.base.knowledge.sort;

import java.util.Random;

/**
 * 快排
 * 时间复杂度
 *  最优：n*logn
 *  最差n*n
 * @author zhouruifeng
 *         create at 2017/3/2.
 */
public final class QuickSort {

    private QuickSort(){

    }

    /**
     * main方法
     * @param args 参数
     */
    public static void main(String[] args){
        int[] a = new int[]{3, 2, 1, 5, 7,8,1,1,12,3,4,5,6};

        quickSort(a);

        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + ",");
        }
    }

    /**
     * http://img.blog.csdn.net/20150602150852238
     * 对数组进行快速排序
     * @param a 数组
     */
    public static void quickSort(int[] a){
        sort(a, 0, a.length-1);
    }

    /**
     * 对数组制定left和right进行快速排序
     * 快速排序采用的思想是分治思想，先找到一个元素作为基准（理论上可以随便找一个，这块是使用的第一个元素作为基准），
     * 然后对数组进行分区，使其左边的元素不大于基准元素，使其右边的元素都不小于基准元素，如此作为基准的元素调整到正确的位置
     * @param a 数组
     * @param left 需要排序的数组开始的index
     * @param right 需要排序的数组的结束index
     */
    public static void sort(int[] a, int left, int right){
        if (left < right){
            int keyIndex = left;
            int key = a[keyIndex];

            int low = left;
            int high = right;
            while (low < high){
                while (low < high && a[high] > key){
                    high--;
                }
                a[keyIndex] = a[high];
                keyIndex = low;

                while (low < high && a[low] < key){
                    low++;
                }
                a[keyIndex] = a[low];
                keyIndex = low;
            }
            //跳出循环后，会low==high，此时空位为low，a[low] = key
            a[low] = key;
            //对key左边的数组再进行排序
            sort(a, left, low-1);
            //对key右边的数组再进行排序
            sort(a, low+1, right);
        }
    }
}
